package com.gxc.tree;

/**
 * 满二叉树   节点的总数量为2的n次方-1
 */
public class FullBinaryTree {

    public static void main(String[] args) {
        TreeBean tree = Preorder.createTree();
        TreeBean tree2 = Preorder.createFullBinaryTree();

        //递归判断是否满二叉树
        FullTreeInfo fullTreeInfo = recursion(tree);
        int count = (int) (Math.pow(2, fullTreeInfo.level)-1);
        System.out.println(count == fullTreeInfo.nodeCount);

        fullTreeInfo = recursion(tree2);
        count = (int) (Math.pow(2, fullTreeInfo.level)-1);
        System.out.println(count == fullTreeInfo.nodeCount);
    }

    /**
     * 递归判断是否满二叉树
     * @param tree
     * @return
     */
    private static FullTreeInfo recursion(TreeBean tree) {
        if (tree == null) {
            return new FullTreeInfo(0, 0);
        }

        //左边树的信息
        FullTreeInfo leftTreeInfo = recursion(tree.left);
        //右边树的信息
        FullTreeInfo rightTreeInfo = recursion(tree.right);

        int curLevel = Math.max(leftTreeInfo.level, rightTreeInfo.level);
        int curNodeCount = leftTreeInfo.nodeCount + rightTreeInfo.nodeCount;
        return new FullTreeInfo(curLevel+1, curNodeCount+1);
    }
}
